/*
 *  Librarie de tipuri de date abstracte (TDA)
 
    Copyright (C) 2007  Catedra de Structuri de Date

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
 
#include <stdlib.h>
#include "graph.h"
#include "arraylist.h"
#include "linkedlist.h" 
#include "linkedqueue.h"
#include "linkedstack.h"

#define INF 0x7ffffff
#define white 0
#define gray 1
#define black 2

/*
 * Global variables
 */

char cycle;
unsigned int time;

/*
 * Structures definitions
 */
 
struct graph_node
{
    unsigned int key;
    double cost;
};
 
struct graph_link
{
    double cost;
    GraphNode node;
};
 
struct graph_adt
{
    unsigned int count;
    ArrayList adjlist;
};

struct link
{
    int source, dest;
    double cost;
};
 
/*
 * Private functions
 */

int _G_BFS(Graph graph, unsigned int s, unsigned int d, unsigned int *p, double **flow)
{
    char *color = (char *)malloc(sizeof(char)*(graph->count+1));
    unsigned int u,v;
    GraphLink result;
    GraphLink node;
    ArrayListIterator it;
    LinkedListIterator il;
    LinkedList l;
    LinkedQueue q = LQ_New();
    
    for (u=1; u<=graph->count; u++)
    {
        color[u] = white; 
    }

    LQ_Enqueue(q, (unsigned int*)s);
    color[s] = gray;
    
    p[s] = 0;
    
    while (LQ_Empty(q) != 1)
    {
        u = (unsigned int)LQ_Front(q);  
        LQ_Dequeue(q);
        color[u] = black;
        
        for (v=1; v<=graph->count; v++)
        {
            if (color[v] == white)
            {
                for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
 	            {  
                    l = (LinkedList)AL_Get(graph->adjlist, it);
                    result = (GraphLink)LL_Get(l,LL_Begin(l));
                
                    if (result->node->key == u)
                    {
                       il = LL_Next(l,LL_Begin(l));
          
                       while (il != LL_End(l)) 
                       {
                           node = (GraphLink)LL_Get(l,il);
                        
                           if (node->node->key == v)
                           {
                               if (node->cost - flow[u][v] > 0)
                               {
                                   LQ_Enqueue(q, (unsigned int *)v);
                                   color[v] = gray;
                                   p[v] = u;
                               }
                               
                               break;
                           }    
                           
                           il = LL_Next(l,il);
                       }
                        
                       break;
                    }                            
                }
            }
        }
    }
    
    if (color[d] == black)
    {
        return 1;
    }
    
    return 0;
}

LinkedList _G_GetNeighbours(Graph graph, unsigned int index)
{
    ArrayListIterator it;
    GraphLink result;
    LinkedList l;
 	
 	for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
 	{
        l = (LinkedList)AL_Get(graph->adjlist, it);
        result = (GraphLink)LL_Get(l, LL_Begin(l));
        
        if (result->node->key == index)
        {
            return l;
        }
    }
}
 
void _G_CoverDFS(Graph graph, unsigned int u, char *c, unsigned int *p, unsigned int *tDesc, unsigned int *tFin, char print)
{
    LinkedList l;
    GraphLink lnk;
    LinkedListIterator it;
     
    c[u] = gray;
    tDesc[u] = ++time;
     
    l = _G_GetNeighbours(graph, u);
           
    for (it=LL_Next(l, LL_Begin(l)); it!=LL_End(l); it=LL_Next(l, it))
    {
        lnk = (GraphLink)LL_Get(l, it);
          
        if (c[lnk->node->key] == white)
        {
            p[lnk->node->key] = u;
            
            if (print == 1)
            {
                printf("%d ",lnk->node->key);
            } 
            
            _G_CoverDFS(graph, lnk->node->key, c, p, tDesc, tFin, print);
        }
    }    
     
    c[u] = black;
    tFin[u] = ++time;
}

void _G_Explore(Graph graph, unsigned int u, unsigned int *top_sort, char *c)
{
    GraphLink lnk; 
    LinkedList l;
    LinkedListIterator it;
    
    c[u] = gray;
    l = _G_GetNeighbours(graph, u);
    
    for (it=LL_Next(l, LL_Begin(l)); it!=LL_End(l); it=LL_Next(l, it))
    {
        lnk = (GraphLink)LL_Get(l, it);
          
        if (c[lnk->node->key] == white)
        {
            _G_Explore(graph, lnk->node->key, top_sort, c);
        }
        
        else
        {
            if (c[lnk->node->key] == gray)
            {
                cycle = 1;
            }
        }
    }
    
    top_sort[time--] = u;
}

void _G_Tarjan(Graph graph, unsigned int u, LinkedList ls, LinkedStack s, char *c, unsigned int *dfs, unsigned int *lowlink)
{
    LinkedListIterator it; 
    LinkedList l;
    GraphLink lnk;
    unsigned int v;
    
    dfs[u] = time; 
    lowlink[u] = time++;
    c[u] = gray;
    
    LS_Push(s, (unsigned int*)u);
    
    l = _G_GetNeighbours(graph, u);
    
    for (it=LL_Next(l, LL_Begin(l)); it!=LL_End(l); it=LL_Next(l, it))
    {
        lnk = (GraphLink)LL_Get(l, it);
          
        if (c[lnk->node->key] == white)
        {
            _G_Tarjan(graph, lnk->node->key, ls, s, c, dfs, lowlink);
            
            if (lowlink[u] > lowlink[lnk->node->key])
            {
                lowlink[u] = lowlink[lnk->node->key];
            }
        }
            
        else
        {
            if (c[lnk->node->key] == gray)
            {
                if (lowlink[u] > dfs[lnk->node->key])
                {
                    lowlink[u] = dfs[lnk->node->key];
                }
            }
        }
    }
    
    if (lowlink[u] == dfs[u])
    {
        l = LL_New();
        do
        {
            v = (unsigned int)LS_Top(s);
            LS_Pop(s);
            c[v] = black;
            LL_Add(l, LL_Begin(l), (unsigned int*)v);
        } 
        while (v != u);
        LL_Add(ls, LL_Begin(ls), l);
    }
}
 
unsigned int _G_CoverAP(Graph graph, unsigned int u, char *c, unsigned int *p, unsigned int *low, unsigned int *tDesc, unsigned int *artic)
{
    unsigned int subtrees;
    LinkedListIterator it;
    LinkedList l;
    GraphLink lnk;
     
    subtrees = 0; 
    c[u] = gray;
    tDesc[u] = ++time;
    low[u] = time;
     
    l = _G_GetNeighbours(graph, u);
           
    for (it=LL_Next(l, LL_Begin(l)); it!=LL_End(l); it=LL_Next(l, it))
    {
        lnk = (GraphLink)LL_Get(l, it);
          
        if (c[lnk->node->key] == white)
        {    
            p[lnk->node->key] = u;
            
            _G_CoverAP(graph, lnk->node->key, c, p, low, tDesc, artic);
            
            subtrees++;
            
            if (low[lnk->node->key] < low[u])
            {
                low[u] = low[lnk->node->key];
            }
            
            if ((p[u] != 0) & (low[lnk->node->key] >= tDesc[u]))
            {
                artic[u] = 1;
            }
        }
        
        else
        {
            if (tDesc[lnk->node->key] < low[u])
            {
                low[u] = tDesc[lnk->node->key];
            }
        }
    }    
     
    c[u] = black;
   
    return subtrees;
} 

unsigned int _G_AP(Graph graph, unsigned int * articulation)
{
    char *color = (char *)malloc(sizeof(char)*(graph->count+1));
    unsigned int *low = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int *parent = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int *start_time = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int u;
    unsigned int count;
     
    for (u=1; u<=graph->count; u++)
    {
        color[u] = white;
        parent[u] = 0;
        start_time[u] = 0;
        articulation[u] = 0;
    }
     
    time = 0;
    count = 0;
     
    for (u=1; u<=graph->count; u++)
    {
        if (color[u] == white)
        {
            if (_G_CoverAP(graph, u, color, parent, low, start_time, articulation) > 1)
            {
                articulation[u] = 1;
				count++;
            }
        }
    }    
    
    return count;
}
 
void _G_CoverBR(Graph graph, unsigned int u, char *c, unsigned int *p, unsigned int *low, unsigned int *tDesc, LinkedList ls)
{
    LinkedListIterator it;
    LinkedList l;
    GraphLink lnk;
     
    c[u] = gray;
    tDesc[u] = ++time;
    low[u] = time;
     
    l = _G_GetNeighbours(graph, u);
           
    for (it=LL_Next(l, LL_Begin(l)); it!=LL_End(l); it=LL_Next(l, it))
    {
        lnk = (GraphLink)LL_Get(l, it);
          
        if (c[lnk->node->key] == white)
        {    
            p[lnk->node->key] = u;
            
            _G_CoverBR(graph, lnk->node->key, c, p, low, tDesc, ls);
            
            if (low[u] > low[lnk->node->key])
            {
                low[u] = low[lnk->node->key];
            }
            
            if (low[lnk->node->key] > tDesc[u])
            {
                l = LL_New();
                LL_Add(l, LL_Begin(l), (unsigned int*)u);                    
                LL_Add(l, LL_End(l), (unsigned int*)lnk->node->key);
                LL_Add(ls, LL_Begin(ls), l);                    
            }
            
            if ((p[u] != lnk->node->key) & (low[u] > tDesc[lnk->node->key]))
            {
                low[u] = tDesc[lnk->node->key];
            }
        }
        
        else
        {
            if (tDesc[lnk->node->key] < low[u])
            {
                low[u] = tDesc[lnk->node->key];
            }
        }
    }    
     
    c[u] = black;
} 

void _G_PrintLL(LinkedList list)
{
    GraphLink result;
    LinkedListIterator il;	
    
    il = LL_Next(list, LL_Begin(list)); 
    
    if (il != LL_End(list))
    { 
	    while (il != LL_End(list)) 
        {
            result = (GraphLink)LL_Get(list, il);
		    printf("%d ", result->node->key);
			
		    il = LL_Next(list, il);
	    }
	    
	    printf("\n");
    }
     
    else 
    {
        printf("null\n");
    }
}
 
void _G_reuneste(Graph graph,int * h,int u,int v)
{
	int i,t;
	t=h[u];
	for(i=0;i<graph->count;i++)
	{
		if(h[i]==t) h[i]=h[v];
	}
}  
 
ArrayListIterator _G_GetNodeIterator(Graph graph, int n)
{
    LinkedList l;
    ArrayListIterator it;
      
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
    {  
        l = (LinkedList) AL_Get(graph->adjlist, it);
        if( ((GraphLink) LL_Get(l,LL_Begin(l)))->node->key == n)
        {
            return it;
        }
    }           
}

int _G_LinkCheck(Graph graph)
{
    LinkedList l;
    ArrayListIterator it;
    LinkedListIterator jt;  
    GraphLink result;    
      
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
    {  
        l = (LinkedList) AL_Get(graph->adjlist, it);
        for (jt=LL_Begin(l) ; jt!=LL_End(l); jt=LL_Next(l,jt))
        {
            result = (GraphLink) LL_Get(l,jt);
            if(((GraphLink) LL_Get(l,jt))->cost < 0)
            {
                return 1;
            }
        }
    }
    
    return 0;
}
 

/*
 * Public functions
 */
 
Graph G_New()
{
    // TODO: adaugarea unui nou parametru pentru numarul maxim de noduri dintr-un graf
    Graph result = (Graph)malloc(sizeof(struct graph_adt));
    
    result->count = 0;
    result->adjlist = AL_New(0);
    
    return result;
}

void G_Free(Graph graph)
{
    if (graph != NULL)
 	{
        AL_Free(graph->adjlist);
 		free(graph);
 	}
}

unsigned int G_GetNodeCount(Graph graph)
{
    return graph->count;
}

GraphLink G_GetNode(Graph graph, unsigned int index)
{           
    ArrayListIterator it;
    GraphLink result;
    GraphNode node;
    LinkedList l;
 	
 	if ((index < 1) | (index > graph->count))
 	{      
        result = (GraphLink)malloc(sizeof(struct graph_link));      
        node = (GraphNode)malloc(sizeof(struct graph_node));
        node->key = -1;
        node->cost = -1; 
        result->node = node;
        result->cost = -1; 
	    return result;     
    }
 	
 	for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
 	{
        l = (LinkedList)AL_Get(graph->adjlist, it);
        result = (GraphLink)LL_Get(l, LL_Begin(l));
        
        if (result->node->key == index)
        {
            return result;
        }
    }
}

unsigned int G_GetEdgeCount(Graph graph)
{
    unsigned int suma; 
    ArrayListIterator it;
    
    suma = 0;
    
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
    {
        suma += LL_Size(AL_Get(graph->adjlist, it))-1;
    }
    
    return suma;
}

int G_IsEmpty(Graph graph)
{
	return (graph->count == 0);
}

void G_AddNode(Graph graph, unsigned int n, double cost)
{
    GraphNode node = (GraphNode)malloc(sizeof(struct graph_node));
    GraphLink lnk = (GraphLink)malloc(sizeof(struct graph_link));
    LinkedList l = LL_New();
  
    node->key = n;
    node->cost = cost;
    
    lnk->node = node;
    lnk->cost = 0;
    
    graph->count++;
      
    LL_Add(l, LL_Begin(l), lnk);
    AL_Add(graph->adjlist, AL_End(graph->adjlist), l);
}

void G_DelNode(Graph graph, unsigned int n)
{
    ArrayListIterator it;
    LinkedListIterator il;
    GraphLink result;
    GraphLink lnk;
    LinkedList l;
      
    lnk = G_GetNode(graph, n);
    
    if (lnk->node->key == -1)
    {
        return;
    }
         
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
 	{  
        l = (LinkedList)AL_Get(graph->adjlist, it);
        result = (GraphLink)LL_Get(l, LL_Begin(l));
         
        if (result->node->key == n)
        {
            AL_Remove(graph->adjlist, it);
        }
        
        else
        {
            for (il=LL_Begin(l); il!=LL_End(l); il=LL_Next(l, il))    
            {
                result = (GraphLink)LL_Get(l, il); 
                
                if (result->node->key == lnk->node->key)
                {
                    LL_Remove(l, il);
                }
            }
        }    
    }
    
    graph->count--;
}

void G_AddLink(Graph graph, unsigned int u, unsigned int v, double cost) 
{
    ArrayListIterator it;
    GraphLink result;
    GraphLink node;
    LinkedList l;
    GraphLink lnk = (GraphLink)malloc(sizeof(struct graph_link));
     
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
 	{
        l = (LinkedList)AL_Get(graph->adjlist, it);
        result = (GraphLink)LL_Get(l,LL_Begin(l));
        
        if (result->node->key == u)
        {             
            node = G_GetNode(graph, v);
            
            if (node->node->key == -1)
            {
                return;
            }
            
            lnk->node = node->node;
            lnk->cost = cost;   
            LL_Add(l, LL_End(l), lnk);              
            return;
        }   
    }
}

void G_DelLink(Graph graph, unsigned int u, unsigned int v)
{
    ArrayListIterator it;
    LinkedListIterator il;
    LinkedList l;
    GraphLink result;
    GraphLink lnk;
    
    lnk = G_GetNode(graph, u);
    if (lnk->node->key == -1)
    {
        return;
    }
    
    lnk = G_GetNode(graph, v);
    if (lnk->node->key == -1)
    {
        return;
    }
     
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
 	{  
        l = (LinkedList)AL_Get(graph->adjlist, it);
        result = (GraphLink)LL_Get(l, LL_Begin(l));
          
        if (result->node->key == u)
        {   
            for (il=LL_Next(l, LL_Begin(l)); il!=LL_End(l); il=LL_Next(l, il))    
            {
                lnk = (GraphLink)LL_Get(l, il); 
                
                if (lnk->node->key == v)
                {
                    LL_Remove(l, il);
                }
            } 
        }  
    }
}

int G_IsLink(Graph graph, unsigned int u, unsigned int v)
{
    ArrayListIterator it;
    LinkedListIterator il;
    LinkedList l;
    GraphLink result;
    GraphLink lnk;
    
    lnk = G_GetNode(graph, u);
    if (lnk->node->key == -1)
    {
        return 0;
    }
    
    lnk = G_GetNode(graph, v);
    if (lnk->node->key == -1)
    {
        return 0;
    }
     
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
 	{  
        l = (LinkedList)AL_Get(graph->adjlist, it);
        result = (GraphLink)LL_Get(l, LL_Begin(l));
          
        if (result->node->key == u)
        {   
            for (il=LL_Next(l, LL_Begin(l)); il!=LL_End(l); il=LL_Next(l, il))    
            {
                lnk = (GraphLink)LL_Get(l, il); 
                
                if (lnk->node->key == v)
                {
                    return 1;
                }
            } 
        }  
    }
    
    return 0;
}

double G_GetLink(Graph graph, unsigned int u, unsigned int v)
{
    ArrayListIterator it;
    LinkedListIterator il;
    LinkedList l;
    GraphLink result;
    GraphLink lnk;
    
    lnk = G_GetNode(graph, u);
    if (lnk->node->key == -1)
    {
        return -1;
    }
    
    lnk = G_GetNode(graph, v);
    if (lnk->node->key == -1)
    {
        return -1;
    }
     
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
 	{  
        l = (LinkedList)AL_Get(graph->adjlist, it);
        result = (GraphLink)LL_Get(l, LL_Begin(l));
          
        if (result->node->key == u)
        {   
            for (il=LL_Next(l, LL_Begin(l)); il!=LL_End(l); il=LL_Next(l, il))    
            {
                lnk = (GraphLink)LL_Get(l, il); 
                
                if (lnk->node->key == v)
                {
                    return lnk->cost;
                }
            } 
        }  
    }
    
    return -1;
}

unsigned int G_InnerDegree(Graph graph, unsigned int n)
{
    int suma; 
    ArrayListIterator it;
    LinkedListIterator il;
    LinkedList l;
    GraphLink result;
    GraphLink lnk;
    
    suma = 0;
    
    lnk = G_GetNode(graph, n);
    if (lnk->node->key == -1)
    {
        return 0;
    }
                 
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
    {
        l = (LinkedList)AL_Get(graph->adjlist, it);    
        result = (GraphLink)LL_Get(l,LL_Begin(l));
        
        if (result->node->key != n)
        {        
            for (il=LL_Next(l, LL_Begin(l)); il!=LL_End(l); il=LL_Next(l, il))    
            {
                lnk = (GraphLink)LL_Get(l, il); 
                
                if (lnk->node->key == n)
                {
                    suma++;
                }
            } 
        }
    }
    
    return suma;    
}

unsigned int G_OuterDegree(Graph graph, unsigned int n)
{
    ArrayListIterator it;
    GraphLink result;
    LinkedList l;
    
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
    {
        l = (LinkedList)AL_Get(graph->adjlist, it);    
        result = (GraphLink)LL_Get(l,LL_Begin(l));
        
        if (result->node->key == n)
        {
           return LL_Size(l)-1;
        }
    }
    
    return 0;    
}

unsigned int G_Degree(Graph graph, unsigned int n)
{
    int suma;
    ArrayListIterator it;
    LinkedListIterator il;
    LinkedList l;
    GraphLink result;
    GraphLink lnk;

    suma = 0;
    
    lnk = G_GetNode(graph, n);
    if (lnk->node->key==-1)
    {
        return 0;
    }
                 
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
    {
        l = (LinkedList)AL_Get(graph->adjlist, it);    
        result = (GraphLink)LL_Get(l,LL_Begin(l));
        
        if (result->node->key == n)
        {
              suma+=LL_Size(l)-1;
        }
        
        else
        {     
            for (il=LL_Next(l, LL_Begin(l)); il!=LL_End(l); il=LL_Next(l, il))    
            {
                lnk = (GraphLink)LL_Get(l, il); 
                
                if (lnk->node->key == n)
                {
                    suma++;
                }
            } 
        }
    }
    
    return suma;    
}

void G_PrintNodes(Graph graph)
{
    ArrayListIterator it;
    LinkedList l;
    GraphLink result;
 	
 	for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
 	{
        l = (LinkedList)AL_Get(graph->adjlist, it);
        result = (GraphLink)LL_Get(l,LL_Begin(l));
        
        printf("%d ",result->node->key);
    }    
    
    printf("\n");
}

void G_PrintEdges(Graph graph) 
{
    unsigned int key;
    ArrayListIterator it;
    LinkedListIterator il;
    GraphLink result;
    LinkedList l;
     
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
 	{  
        l = (LinkedList)AL_Get(graph->adjlist, it);
        result = (GraphLink)LL_Get(l, LL_Begin(l));
        
        key = result->node->key;
        
        il = LL_Next(l, LL_Begin(l));  
        while (il != LL_End(l)) 
        {
            result = (GraphLink)LL_Get(l, il);
            printf("%d-%d cost %4.2f\n", key, result->node->key, result->cost);		
        	il = LL_Next(l, il);
        }
    }  
}
 
void G_Print(Graph graph)
{
    ArrayListIterator it;
    LinkedList l;
    GraphLink result;
 	
 	for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
 	{
        l = (LinkedList)AL_Get(graph->adjlist, it);
        result = (GraphLink)LL_Get(l, LL_Begin(l));
        
        printf("%d -> ", result->node->key);
        _G_PrintLL(l);    
    }    
}

unsigned int G_GetConnectedComponentCount(Graph graph)
{
    char *color = (char *)malloc(sizeof(char)*(graph->count+1));
    unsigned int *parent = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int *start_time = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int *end_time = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int u;
    unsigned int count;
     
    for (u=1; u<=graph->count; u++)
    {
        color[u] = white;
        parent[u] = 0;
        start_time[u] = 0;
        end_time[u] = 0;
    }
     
    time = 0;
    count = 0;
    
    for (u=1; u<=graph->count; u++)
    {
        if (color[u] == white)
        {   
            _G_CoverDFS(graph, u, color, parent, start_time, end_time, 0);
            count++;
        }
    }
    
    return count;
}

void G_PrintConnectedComponent(Graph graph)
{
    char *color = (char *)malloc(sizeof(char)*(graph->count+1));
    unsigned int *parent = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int *start_time = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int *end_time = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int u;
     
    for (u=1; u<=graph->count; u++)
    {
        color[u] = white;
        parent[u] = 0;
        start_time[u] = 0;
        end_time[u] = 0;
    }
     
    time = 0;
    
    for (u=1; u<=graph->count; u++)
    {
        if (color[u] == white)
        {   
            printf("%d ",u);
            _G_CoverDFS(graph, u, color, parent, start_time, end_time, 1);
            printf("\n");
        }
    }
}


/*
 * Frequently used algorithms for graphs
 */


// Breadth First Search
void G_BFS(Graph graph, unsigned int source, unsigned int *parent, unsigned int *distance)
{
    char *color = (char*)malloc(sizeof(char)*(graph->count+1)); 
    unsigned int u;
    LinkedListIterator it;
    GraphLink lnk;
    LinkedList l;
    LinkedQueue q = LQ_New();
    
    for (u=1; u<=graph->count; u++)
    {
        color[u] = white;
        parent[u] = 0;
        distance[u] = INF;
    }
     
    color[source] = gray;
     
    distance[source] = 0;
    LQ_Enqueue(q, (unsigned int*)source);
            
    while (LQ_Empty(q) == 0)
    {
        u = (unsigned int)LQ_Front(q);
        LQ_Dequeue(q);
           
        l = _G_GetNeighbours(graph, u);

        for (it=LL_Next(l, LL_Begin(l)); it!=LL_End(l); it=LL_Next(l, it))
        {
            lnk = (GraphLink)LL_Get(l, it);
               
            if (color[lnk->node->key] == white)
            {  
                color[lnk->node->key] = gray;

                parent[lnk->node->key] = u;

                distance[lnk->node->key] = distance[u] + 1;
               
                LQ_Enqueue(q, (unsigned int*)lnk->node->key);        
            }   
        }
           
        color[u] = black;
    }
}

// Depth First Search
void G_DFS(Graph graph, unsigned int *parent, unsigned int *start_time, unsigned int *end_time)
{
    char *color = (char *)malloc(sizeof(char)*(graph->count+1));
    unsigned int u;
     
    for (u=1; u<=graph->count; u++)
    {
        color[u] = white;
        parent[u] = 0;
        start_time[u] = 0;
        end_time[u] = 0;
    }
     
    time = 0;
    
    for (u=1; u<=graph->count; u++)
    {
        if (color[u] == white)
        {   
            _G_CoverDFS(graph, u, color, parent, start_time, end_time, 0);
        }
    }
}

// Topological Sort
int G_TopSort(Graph graph, unsigned int *top_sort)
{
    char *color = (char *)malloc(sizeof(char)*(graph->count+1));
    unsigned int i;
    
    for (i=1; i<=graph->count; i++)
    {
        color[i] = white;
    }
    
    time = graph->count-1;
    cycle = 0;
    
    for (i=1; i<=graph->count; i++)
    {
        if (color[i] == white)
        {
            _G_Explore(graph, i, top_sort, color);
            
            if (cycle == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}

// Strongly Connected Components
void G_SCC(Graph graph, unsigned int start_node, LinkedList list) 
{
    char *color = (char *)malloc(sizeof(char)*(graph->count+1));
    unsigned int *dfs = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int *lowlink = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int i;
    LinkedStack stack = LS_New();
    
    for (i=1; i<=graph->count; i++)
    {
        color[i] = white;
    }
    
    time = 0;
    
    _G_Tarjan(graph, start_node, list, stack, color, dfs, lowlink);
}

// Articulation Points
unsigned int G_AP(Graph graph, unsigned int *cut_vertex)
{
    char *color = (char *)malloc(sizeof(char)*(graph->count+1));
    unsigned int *articulation = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int *low = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int *parent = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int *start_time = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int u;
    unsigned int count;
     
    for (u=1; u<=graph->count; u++)
    {
        color[u] = white;
        parent[u] = 0;
        start_time[u] = 0;
        articulation[u] = 0;
    }
     
    time = 0;
    count = 0;
     
    for (u=1; u<=graph->count; u++)
    {
        if (color[u] == white)
        {
            if (_G_CoverAP(graph, u, color, parent, low, start_time, articulation) > 1)
            {
                articulation[u] = 1;
            }
        }
    }    
    
    for (u=1; u<=graph->count; u++)
    {
        if (articulation[u] == 1)
        {
            cut_vertex[count++] = u;
        }
    }
  
    return count;
}

// Bridges
void G_BR(Graph graph, LinkedList list)
{
    char *color = (char *)malloc(sizeof(char)*(graph->count+1));
    unsigned int *low = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int *parent = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int *start_time = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
    unsigned int u;
     
    for (u=1; u<=graph->count; u++)
    {
        color[u] = white;
        parent[u] = 0;
        start_time[u] = 0;
    }
     
    time = 0;
     
    for (u=1; u<=graph->count; u++)
    {
        if (color[u] == white)
        {
            _G_CoverBR(graph, u, color, parent, low, start_time, list);
        }
    }       
}

// Biconnected Components
unsigned int G_BiConex(Graph graph)
{
	LinkedList l;
	LinkedListIterator it;
	unsigned int * ap = (unsigned int *)malloc(sizeof(unsigned int) * graph->count);
	unsigned int i, j, count;
	
	_G_AP(graph, ap);
	
	for(i = 1;i <= graph->count;i++)
    {
		count = 0;
		l = _G_GetNeighbours(graph, i);
		for (it = LL_Next(l, LL_Begin(l)); it != LL_End(l); it = LL_Next(l, it))
        {
			count++;
			if(count > 1)
			{
                break;
            }
		}
		
		if(count == 1)
		{
			ap[i] = 1;
        }
	}
	
	count = -1;
	
	for(i = 1;i <= graph->count;i++)
	{
		if(ap[i] == 1)
        {
			l = _G_GetNeighbours(graph, i);
			for (it = LL_Next(l, LL_Begin(l)); it != LL_End(l); it = LL_Next(l, it))
            {
				j = ((GraphLink)LL_Get(l, it))->node->key;
				
				if(ap[j] == 1)
                {
					G_DelLink(graph, i, j);
					count++;
				}
			}
		}
    }
		
	return count;
}

// Floyd - Warshall
void G_FloydWarshall(Graph graph, double **fw)
{
    unsigned int i,j,k,key;
    LinkedList l;
    ArrayListIterator it;
    LinkedListIterator il;
    GraphLink result;

    for (i=1; i<=graph->count; i++)
    {
        for (j=1; j<=graph->count; j++)
        {   
            fw[i][j] = INF;
            
            if (i == j) 
            {
                fw[i][j]=0;
            }        
        }
    }
    
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
 	{  
        l = (LinkedList)AL_Get(graph->adjlist, it);
        result = (GraphLink)LL_Get(l,LL_Begin(l));
        key = result->node->key;

        il = LL_Next(l,LL_Begin(l));
          
        while (il != LL_End(l)) 
        {
            result = (GraphLink)LL_Get(l,il);
            fw[key][result->node->key] = result->cost;	
        	il = LL_Next(l,il);
        }
    }  
      
    for(k=1; k<=graph->count; k++)  
    {
        for (i=1; i<=graph->count; i++)
        {
            for (j=1; j<=graph->count; j++)
            {   
        	    if (fw[i][k] + fw[k][j] < fw[i][j])
				{
                    fw[i][j] = fw[i][k] + fw[k][j];
                }
            }
        }  
    }
}

// Ford - Fulkerson
double G_FordFulkerson(Graph graph, unsigned int source, unsigned int destination)
{
    unsigned int *parent = (unsigned int *)malloc(sizeof(int)*(graph->count+1));
    ArrayListIterator it;
    LinkedListIterator il;
    GraphLink result;
    GraphLink node;
    LinkedList l;
    double **flow;
    double increment;
    double max_flow;
    unsigned int i,j,u;
    
    
    max_flow = 0;
    
    flow = (double**)malloc(sizeof(double*)*graph->count+1);
    for (i=1; i<=graph->count; i++)
    {
        flow[i] = (double*)malloc(sizeof(double)*graph->count+1);
    }
    
    for (i=1; i<=graph->count; i++)
    {
        parent[i] = 0;
        
        for (j=1; j<=graph->count; j++)
        {
            flow[i][j] = 0;
        }
    }
    
    while (_G_BFS(graph, source, destination, parent, flow) == 1)
    {
        increment = INF;  
        
        for (u = destination; parent[u]>0; u = parent[u])
        {	
            for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
 	        {  
                l = (LinkedList)AL_Get(graph->adjlist, it);
                result = (GraphLink)LL_Get(l,LL_Begin(l));
                
                if (result->node->key == parent[u])
                {
                    il = LL_Next(l,LL_Begin(l));
          
                    while (il != LL_End(l)) 
                    {
                        node = (GraphLink)LL_Get(l,il);
                        
                        if (node->node->key == u)
                        {             
                            if (increment > node->cost - flow[parent[u]][u])
                            {
                                increment = node->cost - flow[parent[u]][u];              
                            }
                            
                            break;
                        }
                        
      		            il = LL_Next(l,il);   
                    }
                    
                    break;
                }
            }
        }
        
        for (u=destination; parent[u]>0; u=parent[u]) 
        {
	    	flow[parent[u]][u] += increment;
	    	flow[u][parent[u]] -= increment;
		}
                		
		max_flow += increment;
    }
    
    return max_flow;
}

//Dijkstra
int G_Dijkstra(Graph graph, int s, double *d)
{

     unsigned int *parent = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));
     unsigned int *visited = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));     

     LinkedList l;
     LinkedListIterator it,jt;
     GraphLink result;
     double min;
     int i,u,v;
     int lq=0;
     
     for (i=0; i<graph->count; i++)
     {
         d[i]=INF;
         visited[i]=0;
         parent[i]=0;
         lq++;
     }
     
     if(_G_LinkCheck(graph)==1)
     {
            return 0;
     }
            
     d[s-1]=0;
     while (lq > 0)
     {
            i=0;
            min = INF;
            
            for(v=0; v<graph->count; v++)
            {
                if(d[v]<min && visited[v]==0)
                {
                    min = d[v];
                    u=v; 
                    i=1;                                              
                }
            }       
            
            if(i==0)
            {
                return 0;
            }
            
            visited[u]=1;
            lq--;

            l=(LinkedList) AL_Get(graph->adjlist,u);
            for ( it=LL_Next(l,LL_Begin(l)) ; it!=LL_End(l); it=LL_Next(l,it))
            {
                result = (GraphLink) LL_Get(l,it);
                v = _G_GetNodeIterator(graph,result->node->key);
     
                if(d[u]+result->cost<d[v])
                {
                    d[v]=d[u]+result->cost;
                    parent[v]=u;
                }
            }
      }
      
      return 1;
}

//Bellman Ford
int G_BellmanFord(Graph graph, int s, double * dx)
{
     unsigned int *px = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1));     
     LinkedList l;
     int i,nod1,nod2,j,k;
     double cost;
     
     for (i=0; i<graph->count; i++)
     {
         dx[i]=INF;
         px[i]=0;
     }
     
     dx[s-1]=0;

     for(i=0;i<graph->count; i++)
     {
        for(j=0;j<graph->count; j++)
        {
            for(k=0;k<graph->count; k++)
            {
                                                             
                l = (LinkedList) AL_Get(graph->adjlist,k);
                nod2 = ((GraphLink) LL_Get(l,LL_Begin(l)))->node->key;
                   
                l = (LinkedList) AL_Get(graph->adjlist,j);
                nod1 = ((GraphLink) LL_Get(l,LL_Begin(l)))->node->key;
                     
                cost = G_GetLink(graph,nod1,nod2);
                if(cost!=-1)
                {
                    if(dx[k]>dx[j]+cost)
                    {
                       dx[k]=dx[j]+cost;
                       px[k]=j;
                    }                  
                }
            }
        }
    }   
     
    for(j=0;j<graph->count; j++)
    {
        for(k=0;k<graph->count; k++)
        {
                                                             
            l = (LinkedList) AL_Get(graph->adjlist,k);
            nod2 = ((GraphLink) LL_Get(l,LL_Begin(l)))->node->key;
                   
            l = (LinkedList) AL_Get(graph->adjlist,j);
            nod1 = ((GraphLink) LL_Get(l,LL_Begin(l)))->node->key;
              
            cost = G_GetLink(graph,nod1,nod2);
            if(cost!=-1)
            {
                if(dx[k]>dx[j]+cost)
                {
                    return 0; 
                }
            }
        }
    } 
     
    return 1;
}

//Kruskal
double G_Kruskal(Graph graph, int *p)
{
    LinkedList l;
    ArrayListIterator it;
    LinkedListIterator jt;
    GraphLink result;
    struct link aux;
    struct link * e = (struct link *)malloc(sizeof(struct link)*(G_GetEdgeCount(graph)+1));
    unsigned int *h = (unsigned int *)malloc(sizeof(unsigned int)*(graph->count+1)); 
      
    int i,j;
    int n=0;
    double cost=0;
           
    for(i=0;i<graph->count;i++)
    {
        p[i]=-1;
        h[i]=i;
    }     
       
    for (it=AL_Begin(graph->adjlist); it!=AL_End(graph->adjlist); it=AL_Next(graph->adjlist, it)) 
    {  
        l = (LinkedList) AL_Get(graph->adjlist, it);
        for (jt=LL_Next(l,LL_Begin(l)) ; jt!=LL_End(l); jt=LL_Next(l,jt))
        {
            result = (GraphLink) LL_Get(l,jt);
            e[n].source = it;
            e[n].dest = _G_GetNodeIterator(graph,result->node->key);
            e[n].cost = result->cost;
            n++;
        }
    }

    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
			if(e[i].cost>e[j].cost) 
			{
				aux=e[i];
				e[i]=e[j];
				e[j]=aux;
			}
        }      
    }
      
  	for(i=0;i<n;i++)
    {
		if( h[e[i].source]!=h[e[i].dest])
        {
		 	_G_reuneste(graph,h,e[i].source,e[i].dest);
		 	p[e[i].dest] = e[i].source+1;
		 	cost=cost+e[i].cost;
        }
    }
      
    return cost;
}


//Prim
double G_Prim(Graph graph, int s, int *p)
{
    LinkedList l;
    LinkedListIterator jt;
    GraphLink result;
      
	int i,j,u,v,nrVarfuri,imin;
    double cost=0;
	double cmin;
	double * d = (double *)malloc(sizeof(double)*(graph->count+1));
	int * H =(int *) malloc(sizeof(int)*(graph->count+1)); 
	
	nrVarfuri = graph->count;
    for(u=0;u<graph->count;u++)
    {
		d[u]=INF;
		p[u]=-1;
		H[u]=1;					
	}
	
	d[s-1]=0;
	while(nrVarfuri>0)
    {
		cmin=INF;
		imin=-1;
		
		for(i=0;i<graph->count;i++)
		{
			if(H[i]==1 && d[i]<cmin)
			{
				cmin=d[i];
				imin=i;	
			}
		}
		
		if (imin==-1)
        { 
            break;//return -1;
        }
        
		u=imin;
		nrVarfuri--;
		H[u]=0;					
				
        l = (LinkedList) AL_Get(graph->adjlist, (ArrayListIterator) u );
        
        for (jt=LL_Next(l,LL_Begin(l)) ; jt!=LL_End(l); jt=LL_Next(l,jt))
        {
               result = (GraphLink) LL_Get(l,jt);
               v = _G_GetNodeIterator(graph,result->node->key);
               
		       if(result->cost<d[v])
		       {
                   d[v]=result->cost;
			       p[v]=u;
		        }
         }
	}
	
	for(i=0;i<graph->count;i++)
    {
        if(p[i]!=-1) 
        {
            p[i]++;
        }
    
        if (d[i] == INF)
        {
            return -1;     
        }
        
        cost=cost+d[i];                 
    }
    
	return cost;
}
